/*
 * @Author: szx
 * @Date: 2021-10-28 10:55:21
 * @LastEditTime: 2021-11-05 14:14:08
 * @Description:
 * @FilePath: \leetcode\1-99\46\46.cpp
 */

#include <iostream>
#include <vector>
using namespace std;
class Solution {
   public:
    //全排列1
    // 填n个空格，每个数字只能够填一次，填完之后还要填写回来
    void backtrack(vector<vector<int>>& res, int start, vector<int>& nums) {
        if (start >= nums.size()) res.push_back(nums);
        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);
            backtrack(res, start + 1, nums);
            swap(nums[start], nums[i]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        backtrack(res, 0, nums);
        return res;
    }

    // STL方法？
    // vector<vector<int>> permute(vector<int>& nums) {
    //     sort(nums.begin(), nums.end());
    //     vector<vector<int>> ans = {nums};
    //     while (next_permutation(nums.begin(), nums.end()))
    //     ans.push_back(nums); return ans;
    // }
};

class Solution {
   public:
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(0, nums);
        return res;
    }

    void dfs(int cur, vector<int>& nums) {
        if (cur >= nums.size()) res.emplace_back(nums);

        for (int i = cur; i < nums.size(); i++) {
            swap(nums[cur], nums[i]);
            dfs(cur + 1, nums);
            swap(nums[cur], nums[i]);
        }
    }
};
int main() { return 0; }